package com.csdemos.algs;

public class BinaryTree {
	
	public static class Node {
		
		public int value;
		public Node left;
		public Node right;
		public Node parent;
		
		public Node(int value) {
			this.value = value;
		}
		
	}
	
	private Node root;
	
	public BinaryTree() {
		root = null;
	}
	
	public String inorderTreeWalk(Node node) {
		if (node != null) {
			return inorderTreeWalk(node.left) + " " + node.value + " " + inorderTreeWalk(node.right);
		} else {
			return "";
		}
	}
	
	public String preorderTreeWalk(Node node) {
		if (node != null) {
			return node.value + " " + preorderTreeWalk(node.left) + " " + preorderTreeWalk(node.right);
		} else {
			return "";
		}
	}
	
	public String postorderTreeWalk(Node node) {
		if (node != null) {
			return postorderTreeWalk(node.left) + " " + postorderTreeWalk(node.right) + " " + node.value;
		} else {
			return "";
		}
	}
	
	public String parenthesisTreeWalk(Node node) {
		if (node != null) {
			return "(" + parenthesisTreeWalk(node.left) + " " + node.value + " " + parenthesisTreeWalk(node.right) + ")";
		} else {
			return "()";
		}
	}
	
	public Node treeSearch(Node x, int k) {
		if (x == null || k == x.value) {
			return x;
		}
		if (k < x.value) {
			return treeSearch(x.left, k);
		} else {
			return treeSearch(x.right, k);
		}
	}
	
	public Node iterativeTreeSearch(Node x, int k) {
		while (x != null && k != x.value) {
			if (k < x.value) {
				x = x.left;
			} else {
				x = x.right;
			}
		}
		return x;
	}
	
	public int treeMinimum() {
		return treeMinRecursive(root);
	}
	
	public int treeMinRecursive(Node node) {
		if (node == null) {
			throw new IllegalArgumentException("Tree is empty!");
		}
		if (node.left == null) {
			return node.value;
		} else {
			return treeMinRecursive(node.left);
		}
	}
	
	public Node iterativeTreeMinimum(Node x) {
		if (x == null) {
			return x;
		}
		while (x.left != null) {
			x = x.left;
		}
		return x;
	}
	
	public Node iterativeTreeMaximum(Node x) {
		if (x == null) {
			return x;
		}
		while (x.right != null) {
			x = x.right;
		}
		return x;
	}
	
	public int treeMaximum() {
		return treeMaxRecursive(root);
	}
	
	public int treeMaxRecursive(Node node) {
		if (node == null) {
			throw new IllegalArgumentException("Tree is empty!");
		}
		if (node.right == null) {
			return node.value;
		} else {
			return treeMinRecursive(node.right);
		}
	}
	
	public Node treeSuccessor(Node x) {
		if (x.right != null) {
			return iterativeTreeMinimum(x.right);
		}
		Node y = x.parent;
		while (y != null && x == y.right) {
			x = y;
			y = y.parent;
		}
		return y;
	}
	
	public Node treePredecessor(Node x) {
		if (x.left != null) {
			return iterativeTreeMaximum(x.left);
		}
		Node y = x.parent;
		while (y != null && x == y.left) {
			x = y;
			y = y.parent;
		}
		return y;
	}
	
	public void treeInsert(Node z) {
		Node y = null;
		Node x = root;
		while (x != null) {
			y = x;
			if (z.value < x.value) {
				x = x.left;
			} else {
				x = x.right;
			}
		}
		z.parent = y;
		if (y == null) {
			root = z;
		} else if (z.value < y.value) {
			y.left = z;
		} else {
			y.right = z;
		}
	}
	
	public Node treeDelete(Node z) {
		Node y = null;
		Node x = null;
		if (z.left == null || z.right == null) {
			y = z;
		} else {
			y = treeSuccessor(z);
		}
		if (y.left != null) {
			x = y.left;
		} else {
			x = y.right;
		}
		if (x != null) {
			x.parent = y.parent;
		}
		if (y.parent == null) {
			root = x;
		} else if (y == y.parent.left) {
			y.parent.left = x;
		} else {
			y.parent.right = x;
		}
		if (y != z) {
			z.value = y.value;
		}
		return y;
	}
	
	public Node getRoot() {
		return root;
	}
	
	public void setRoot(Node root) {
		this.root = root;
	}
}
